#include "myTree.h"
#include <string.h>
#include <iostream>
#include <functional>
#include <algorithm>

using namespace std;


// 用于返回引用的一个共享 "空结点"，当 locateNode 找不到目标时返回这个引用
static TreeNode NULL_NODE('\0', nullptr, nullptr, Link, Link);

void TreeNode::printNode()
{
    cout << this->data;
}


TreeNode::TreeNode(char a, TreeNode* l, TreeNode* r , NodeTag nl = Link, NodeTag nr = Link){
    data = a;
    leftChild = l;
    rightChild = r;
    lTag = nl;
    rTag = nr;

}

TreeNode::~TreeNode(){
    // 析构函数不在这里删除子节点,由destory管理
}

MyTree::MyTree() {
    root = nullptr;  //空树的核心，根节点为nullptr
    ptr = nullptr;
    prevnode = nullptr;
    isThread = false;  //空树不是线索树
}

//栈


/*void MyStack::printStack(){
    listNode* p = topNode;
     
    
    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}*/

listNode::listNode()
{
    next = nullptr;
    tree = nullptr;
}

listNode::listNode(TreeNode * nodeData, listNode* succ){
    tree = nodeData;
    next = succ;

}

MyStack::MyStack(){
    topNode = nullptr;
    stackSize = 0;
}

MyStack::~MyStack(){
    while(topNode != nullptr){
        listNode* p;
        p = topNode;
        topNode = p ->next;
        delete p;
    }//一个一个删

    stackSize = 0;
}

bool MyStack::push(TreeNode * i ){
    
    listNode * newn = new listNode(i , topNode);
    if(newn == nullptr){return false;}//地址分配失败

    topNode = newn;


    stackSize ++;
    return true;
}

bool MyStack::pop(TreeNode* & i){

    if(topNode == nullptr){return false;}//空栈

    i = topNode->tree;

    listNode *p = topNode;
    topNode = topNode ->next;
    delete p;
    stackSize--;
    return true;
}

bool MyStack::getTop(TreeNode * & i){
    if(topNode == nullptr){return false;}//空栈

    i = topNode ->tree;
    return true;
}

bool MyStack::isEmpty(){
    return (topNode == nullptr);
}



TreeNode* MyTree::creatbitree(){
    if(*ptr == '@'){//查到@

        ptr++;//下一个字符
        return nullptr;//递归退出条件之一
    }

    //字符不为@
    char ch = *ptr;//读
    ptr++;

    TreeNode *left = creatbitree();
    TreeNode *right = creatbitree();
    
    return new TreeNode(ch, left, right, Link, Link);//递归退出条件之二：创建成功

}


MyTree::MyTree(const char a[] ) : root(nullptr), isThread(false){//初始化赋值
   
    if(a == nullptr || strlen(a) ==0){return;}
    ptr = a;//这样可以用递归
    root = creatbitree();
    prevnode = nullptr;
}

void MyTree::destroyTree(TreeNode* rt)
{
    // 递归终止条件,当前节点为空
    if (!rt) return;

    // 若不是线索二叉树，或当前节点的左标记为link
    // 说明左是真实子节点，递归销毁左子树
    if (!isThread || rt->lTag == Link) destroyTree(rt->leftChild);

    // 同理，递归销毁右子树
    if (!isThread || rt->rTag == Link) destroyTree(rt->rightChild);

    // 左右子树均销毁后，释放当前节点的内存
    delete rt;
}

MyTree::~MyTree()
{
    destroyTree(root);
    root = nullptr;
}


TreeNode* MyTree:: copy(TreeNode * t){//递归关键函数

    if(t == nullptr){
        return nullptr;//返回
    }

    TreeNode * temp = new TreeNode( t->data, nullptr ,nullptr);//开

    
    if(t->lTag == Link){  
        temp->leftChild = copy(t->leftChild); }//关联
    else {
        temp->leftChild = nullptr; //线索指针丢弃，
    }

    if(t->rTag == Link){  temp->rightChild = copy(t->rightChild); }//防线索树崩溃
     else {
        temp->rightChild = nullptr; // 线索指针丢弃，
    }
    return temp;

}

MyTree::MyTree(const MyTree& i){
    if(i.root == nullptr){
        root = nullptr;
        ptr = nullptr;
        prevnode = nullptr;
        return;
    }

    isThread = false;
    
    root = copy(i.root);//为了用递归

    ptr = nullptr;
    prevnode = nullptr;

}   

void MyTree::preOrderTraverse(){

    MyStack s;//工作栈

    TreeNode *cur = root;

    while(cur != nullptr || !s.isEmpty()){
        while(cur != nullptr){

            cur->printNode();//见到一个，访问一个，然后进左压栈
            s.push(cur);//会有多余压栈行为，但是问题不大
            if(cur->lTag == Link){//防线索树索引导致崩溃
                cur = cur->leftChild;//进左子树
            }
            else{cur = nullptr;}
        }

        if(!s.isEmpty()){
            s.pop(cur);
            if(cur->rTag == Link){
                cur = cur->rightChild;//弹栈说明左子树访问完了，该右边了
            }
            else{cur = nullptr;}//有索引说明到头了
            
        }
    }


}

void MyTree:: inOrderTraverse(){//见到一个节点先不访问，先压栈

    MyStack s;
    TreeNode *cur = root;

    while(cur != nullptr || !s.isEmpty()){
        
        while(cur != nullptr){
            s.push(cur);//先压栈
            if(cur->lTag == Link){//防线索树索引导致崩溃
                cur = cur->leftChild;//进左子树
            }
            else{cur = nullptr;}
        }

        if(!s.isEmpty()){
            s.pop(cur);//弹一个
            cur->printNode();//访问
            if(cur->rTag == Link){
                cur = cur->rightChild;//弹栈说明左子树访问完了，该右边了
            }
            else{cur = nullptr;}//有索引说明到头了
        }
    }

}

void MyTree::postOrderTraverse(){
    MyStack s;

    TreeNode * cur = root;//当前访问的结点
    TreeNode * prev = nullptr;//上一个访问的的结点
    TreeNode * top = nullptr;//栈顶节点

    while(cur != nullptr || !s.isEmpty()){

        while(cur != nullptr){
            s.push(cur);//先压�?
            if(cur->lTag == Link){//防线索树索引导致崩溃
                cur = cur->leftChild;//进左子树
            }
            else{cur = nullptr;}
        }

        if(!s.isEmpty()){
            s.getTop(top);//取但不弹

            bool rit = (top->rTag == Thread);//检测是否是线索

            if(top->rightChild == nullptr || prev == top->rightChild || rit  ){//条件：右子树为空，或者右子树已经访问过，或者右子是线索
                //可访问
                s.pop(top);
                top->printNode();
                prev = top;
                cur = nullptr;// 当前节点处理完，下一轮从栈顶�?

            }   
            else{//右子树未处理，移到右子节点继续处�?
                cur = top->rightChild;
            }
        }
    }
    
}

TreeNode& MyTree:: locateNode(const char& v){
     //在树中找到值为v的节点则返回该节点，否则返回NULL，支持普通二叉树与线索二叉树
    //直接照搬前序遍历

    MyStack s;//工作�?

    TreeNode *cur = root;

    while(cur != nullptr || !s.isEmpty()){
        while(cur != nullptr){

            if(cur->data == v){
                return *cur;
            };//见到一个，访问一个，然后进左压右
            s.push(cur);//会有多余压栈行为，但是问题不大
            if(cur->lTag == Link){//防线索树索引导致崩溃
                cur = cur->leftChild;//进左子树
            }
            else{cur = nullptr;}
        }

        if(!s.isEmpty()){
            s.pop(cur);
            if(cur->rTag == Link){
                cur = cur->rightChild;//弹栈说明左子树访问完了，该右边了
            }
            else{cur = nullptr;}//有索引说明到头了
            
        }
    }
    return NULL_NODE;
     
}

int MyTree:: leafcount(TreeNode * T){

    int i,j;
    if(!T) {return 0;}

    else if(T->leftChild == nullptr && T->rightChild == nullptr){
        return 1;
    }

    else{
        i = leafcount(T->leftChild);
        j = leafcount(T->rightChild);

        return i+j;

    }

}

int MyTree::countLeaf(){

    TreeNode * T = root;

    return leafcount(T);
    
}

int MyTree::heightcount(TreeNode * T){
    if(T== nullptr){ return 0;}
    else{
        int m = heightcount(T->leftChild);
        int n = heightcount(T->rightChild);
        return (m > n) ? m +1 : n+ 1;
    }
}

int MyTree:: countHeight(){

    TreeNode *T = root;
    return heightcount(T);

}


bool MyTree:: isThreadedTree(){
    return isThread;
}

bool MyTree::inOrderThreading()
{
    if (!root) return false;
    
    if (isThread) return true;

    TreeNode* prev = nullptr;
    // 使用中序遍历的递归变体来建立线索：维护上一个访问的结点 prev
    // 对于没有左子树的结点，将 lTag 设置为 Thread 并指向 prev
    // 对于 prev 没有右子树的结点，设置 prev.rTag 为 Thread 并指向 cur
    std::function<void(TreeNode*)> threadRec = [&](TreeNode* cur) {
        if (!cur) return;
        // left
        if (cur->lTag == Link) threadRec(cur->leftChild);

        // 处理当前结点
        // 如果当前结点没有左孩子，则把左指针当成线索指向前驱；否则保持 Link
        if (!cur->leftChild) {
            cur->lTag = Thread;
            cur->leftChild = prev;
        } else {
            cur->lTag = Link;
        }

        if (prev) {
            // 如果 prev 没有右孩子，prev 的右指针当成线索指向当前结点
            if (!prev->rightChild) {
                prev->rTag = Thread;
                prev->rightChild = cur;
            } else {
                prev->rTag = Link;
            }
        }
        prev = cur;

        // right
        if (cur->rTag == Link) threadRec(cur->rightChild);
    };

    // 为了避免之前的线索信息影响，先把所有结点的 tag 重置为 Link
    std::function<void(TreeNode*)> resetTags = [&](TreeNode* t) {
        if (!t) return;
        t->lTag = Link; t->rTag = Link;
        if (t->leftChild) resetTags(t->leftChild);
        if (t->rightChild) resetTags(t->rightChild);
    };
    resetTags(root);

    threadRec(root);
    // 遍历完成后，prev 指向中序序列的最后一个结点，设置其右线索为 nullptr
    if (prev) {
        prev->rTag = Thread;
        prev->rightChild = nullptr;
    }

    isThread = true;
    return true;
}


TreeNode& MyTree::preNode(const TreeNode &t)
{
    if (!isThread) return NULL_NODE;
    TreeNode &nodeInTree = locateNode(t.data);
    if (&nodeInTree == &NULL_NODE) return NULL_NODE;
    TreeNode* p = &nodeInTree;
    // 如果结点的左指针是线索，则直接返回 leftChild
    if (p->lTag == Thread) {
        if (p->leftChild) return *(p->leftChild);
        return NULL_NODE;
    }
    // 否则前驱就是左子树中最右（最靠后的）结点
    TreeNode* cur = p->leftChild;
    if (!cur) return NULL_NODE;
    while (cur->rTag == Link && cur->rightChild) cur = cur->rightChild;
    return *cur;
}

TreeNode& MyTree::nextNode(const TreeNode &t)
{
    if (!isThread) return NULL_NODE;
    TreeNode &nodeInTree = locateNode(t.data);
    if (&nodeInTree == &NULL_NODE) return NULL_NODE;
    TreeNode* p = &nodeInTree;
    // 如果右指针是线索，则直接返回 rightChild
    if (p->rTag == Thread) {
        if (p->rightChild) return *(p->rightChild);
        return NULL_NODE;
    }
    TreeNode* cur = p->rightChild;
    if (!cur) return NULL_NODE;
    // 否则后继为右子树中最左（最靠前）的结点
    while (cur->lTag == Link && cur->leftChild) cur = cur->leftChild;
    return *cur;
}


HuffmanTree::HuffmanTree(const int &nn, const int arr[])
{
    n = (nn > 0 ? nn : 0);
    weights = nullptr;
    codes.clear();
    if (n <= 0) return;
    weights = new int[n];
    for (int i = 0; i < n; ++i) weights[i] = arr[i];

   
    int m = 2 * n - 1;
    vector<int> parent(m + 1, 0), lchild(m + 1, 0), rchild(m + 1, 0);
    vector<int> w(m + 1, 0);
    // 1-based indexing for classical Huffman
    for (int i = 1; i <= n; ++i) w[i] = weights[i - 1];
    // 初始化临时权重数组。非叶子结点在构造前先用较大值占位，后续会覆盖。
    for (int i = n + 1; i <= m; ++i) w[i] = INT_MAX; // placeholder

    for (int i = n + 1; i <= m; ++i) {
        int s1 = 0, s2 = 0;
        int min1 = INT_MAX, min2 = INT_MAX;
        // 在 1..i-1 中找两个未被选中（parent==0）且权值最小的结点 s1, s2
        for (int j = 1; j < i; ++j) {
            if (parent[j] == 0) {
                if (w[j] < min1) { min2 = min1; s2 = s1; min1 = w[j]; s1 = j; }
                else if (w[j] < min2) { min2 = w[j]; s2 = j; }
            }
        }
        if (s1 == 0 || s2 == 0) break;
        parent[s1] = i; parent[s2] = i;
        lchild[i] = s1; rchild[i] = s2;
        w[i] = w[s1] + w[s2];
    }

    // 叶子结点编码生成：对每个叶子从其向上回溯到根，左子结点记为 '0'，右子结点记为 '1'，
    // 由于我们构造时将较小值放左，较大值放右，因此编码也会体现这一结构。
    codes.assign(n, string());
    for (int i = 1; i <= n; ++i) {
        string code = "";
        int c = i;
        int p = parent[c];
        while (p != 0) {
            if (lchild[p] == c) code = '0' + code;
            else code = '1' + code;
            c = p;
            p = parent[c];
        }
        codes[i - 1] = code;
    }
}

HuffmanTree::~HuffmanTree()
{
    if (weights) delete [] weights;
    weights = nullptr;
}

void HuffmanTree::printHuffmanCodes()
{
    if (n <= 0) return;
    
    vector<pair<int,string>> items;
    for (int i = 0; i < n; ++i) items.push_back({weights[i], codes[i]});
    sort(items.begin(), items.end(), [](const pair<int,string>& a, const pair<int,string>& b){
        return a.first > b.first; 
    });
    for (auto &it : items) {
        cout << it.first << ":" << it.second << endl;
    }
}